Advantages in electronic circuit technology have greatly increased the speed at which central processing unit ("CPU") components of a computer system operate. CPU integrated circuits having cycle times in excess of 60 MHz are now widely available. System components such as random access memories ("RAMs") are typically constructed using the same technologies, and thus, their cycle times match the speeds of the central processing unit components.
The speed with which secondary storage devices, such as disk drives, operate is generally slower than that of the other components in the computer system. The time to complete a disk access is largely dominated by the time required for mechanical drive components to move a read/write head to the proper location relative to the disk and the time for the storage location to rotate under the head. Once the head is in position over the storage location, it performs the remainder of the read or write operation at speeds comparable to those of the components of the CPU.
The time required to position the read/write head over the storage location is commonly referred to as seek time. Fast disk drives have seek times generally in the range of 8-10 milliseconds and are thus several orders of magnitude longer than the time required for the head integrated circuit components to retrieve data from the disk or store data on the disk.
Data are recorded on the disks in concentric tracks, which are divided into sectors. Each sector holds a block of data. A block is the smallest quantity of data which can be written to a disk. A "chunk," which consists of a number of adjacent blocks, is the largest quantity of data written to a disk in a single write operation without performing a seek operation to re-position the read/write head. Chunks vary in size from system to system, depending on the architecture of the system and the applications performed by the system.
A write operation that involves a single block of data is inefficient, since very little data is stored after a time-consuming seek operation. One way to increase the efficiency of the system is to retain the data blocks to be written to the disk in a buffer, accumulate a number of blocks and include them in a disk write operation. The accumulated blocks must be intended for contiguous storage locations on the disk to be included in the write operation, however, Such blocks are referred to as "adjacent blocks." Buffers for accumulating these data blocks are commonly referred to as write caches.
Write caches, which must be non-volatile memories to protect the data from loss or corruption before they are stored on the storage device, are expensive. Accordingly, many systems use relatively small write caches. Further, these caches must be carefully managed to prevent loss of data and also to ensure that the efficiencies and advantages of including the cache in the system are not lost. This is particularly true because the data blocks held in the cache are not ordinarily held in the order in which they are to be stored on the disk. As data blocks are included in various write operations, the cache storage locations in which they were retained are freed. When data blocks are later added to the write cache they are placed in the free locations, which may or may not be contiguous. Generally, the locations are not contiguous and the data blocks are thus "scattered" throughout the cache.
It has been known for some time that requests for data from a disk typically are directed to related data, such as data files. These data files are often written to the disk in a single write operation and are stored in a number of physically adjacent sectors, or disk storage locations. Accordingly, a principle of "locality of reference" has developed among computer programmers which states: when data stored or to be stored at one location are accessed, there is a high probability that data stored or to be stored at physically adjacent locations will be accessed soon thereafter.
To take advantage of this principle, data to be written to a disk are held for a time in the write cache, so that they can be accessed relatively quickly, that is, without performing a disk read operation to retrieve them from the disk. Since it is likely that these data will be accessed relatively soon after they are sent for storage, the use of the cache speeds up the overall operation of the system. The system must keep track of which data blocks are held in the write cache to direct requests for these to the write cache instead of the disk.
Once the write cache is filled, the system performs one or more write operations to transfer data from the cache to the disk drive for storage therein. There are several techniques for managing the orderly transfer of data from the write cache to the drive. One known technique is to include in a disk write operation a search of the write cache for an adjacent data block. If an adjacent block is found, the system transfers both blocks to the disk as part of the disk write operation. This reduces the overall number of disk accesses, and thus, the overall number of the time-consuming seek operations.
Another technique for managing the write cache involves keeping a "least recently used" (LRU) queue. The LRU queue contains a list of blocks in their order of use. The LRU queue identifies blocks by their time of use and their "virtual block numbers," which are numbers associated with the intended storage locations of the blocks on the disk. Since it is likely that the system will access blocks which were more recently used before it again accesses the least recently used blocks, the system transfers these least recently used blocks to the disk while retaining the more recently used blocks in the cache for quick access by the CPU.
The techniques discussed above for managing the transfer of data from the write cache to the disk handle data in quantities of one or two blocks. They thus may not satisfactorily enhance the speed with which the system performs write operations. Accordingly, a technique which includes more data per write operation is needed.
Computer systems are more and more using arrays of disk drives, commonly referred to as Redundant Arrays of Inexpensive Disks, or "RAIDs." RAIDs are described by Patterson et al. in a report No. UCB/CSD87/891, December, 1987, Computer Science Division (EECS), Berkley, Calif. In various RAID architectures, data distributed over "n" drives is encoded to generate redundancy information for error protection and the redundancy information is stored on an n+1st drive. This provides error protection of the data in the event of the corruption or failure of one of the RAID drives.
Each write operation involves 4 disk accesses, 2 to retrieve data and old redundancy information for encoding, and 2 to store the data and the redundancy information. The time to perform a write operation in a RAID is increased over that of a write operation to a single drive, since the heads on the various drives must each be properly positioned. Such systems thus trade overall speed for data security.
Techniques for increasing the efficiency of write operations are needed for RAID systems. While either of the techniques discussed above for managing a write cache provide certain benefits to the RAID systems, a technique for including more data per write operation would rather dramatically increase the efficiency of the RAID system.